package com.ls.daily;

import java.util.ArrayList;
import java.util.List;

public class AddOneRow {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        // 如果root == null，直接返回一个值为val的节点
        if (root == null) {
            return new TreeNode(val);
        }
        // depth=1的情况
        if (depth == 1) {
            return new TreeNode(val, root, null);
        }

        // 先找到地depth-1层所有的节点
        List<TreeNode> now = new ArrayList<>();
        List<TreeNode> next = new ArrayList<>();
        now.add(root);
        while(depth > 2) {
            depth -= 1;
            for (TreeNode temp : now) {
                if (temp.left  != null) {
                    next.add((temp.left));
                }

                if (temp.right != null) {
                    next.add(temp.right);
                }
            }
            now.clear();
            now.addAll(next);
            next.clear();
        }

        // 此时now中为depth - 1的所有节点
        for (TreeNode temp : now) {
            // 新增左节点
            TreeNode t1 = new TreeNode(val);
            // 新增右节点
            TreeNode t2 = new TreeNode(val);
            if (temp.left != null) {
                t1.left = temp.left;
            }

            if (temp.right != null) {
                t2.right = temp.right;
            }

            temp.left = t1;
            temp.right = t2;
        }

        return root;
    }
}
